A Message Authentication Code (hereinafter, referred to as “message authentication” or “MAC”) scheme is a technique for assuring the authenticity of a message by attaching, to the message, a tag that can be computed only by a person who knows a secret key. The use of the message authentication scheme enables, for example, detection of falsification committed by a third party during communication between two parties sharing a secret key.
Specifically, when a sender transmits a message and a tag to a receiver, the receiver computes a tag from the received message and determines whether the computed tag matches the received tag. By doing so, the receiver is able to determine whether the message is from a legitimate transmission source.
Fundamentals of input and output of MAC will be described. A case of transmitting a message M from Alice to Bob between two persons Alice and Bob sharing a secret key K will be described. Alice applies a MAC function MAC_K using K to M, obtains an authentication tag T=MAC_K(M), and transmits a message (M, T) to Bob.
Assume information received by Bob is (M′, T′). Bob is able to know whether the received message (M′, T′) is a pair with the message and the authentication tag transmitted by Alice or not by determining whether T′ matches MAC_K(M′). Accordingly, checking an existence of falsification can be possible.
Examples of such a scheme include a Cipher-based MAC (CMAC) in NPL 1 and a Hash-based MAC (HMAC) in NPL 2.
When using general message authentication, it is difficult to obtain information relating to a falsified position in a message. This is because a value of an authentication tag takes a random value that is different from a correct value when falsification is committed.
In regard to this, a technique is generally used that enables section-to-section checking by dividing a message into arbitrary sections and applying a MAC function to each of the sections, instead of applying a MAC function once to an entire message. By using this technique, a position of falsification committed on a message can be identified.
For example, when a message M is composed of m items M[1], . . . , M[m], a tag is obtained for each of the items as follows.
            T      ⁡              [        1        ]              =          MAC_K      ⁢              (                  M          ⁡                      [            1            ]                          )              ,          ⁢            T      ⁡              [        2        ]              =          MAC_K      ⁢              (                  M          ⁡                      [            2            ]                          )              ,          ⁢  …  ⁢          ,          ⁢            T      ⁡              [        m        ]              =          MAC_K      ⁢              (                  M          ⁡                      [            m            ]                          )            Then, (M, T[1], . . . , T[m]) is transmitted to a receiver. The receiver is able to identify a falsified position based on received (M, T[1], . . . , T[m]).
Examples of the method include applying MAC to data in a hard disk for each file or each disk sector. However, in the method, since m tags are generated with respect to m items, there is a problem of large increase in the amount of data to be stored.
On the other hand, as described in NPL 3, there is an approach that decomposes a message into a plurality of different-length subsequences that may overlap mutually, and applies a MAC to each of the subsequences.
For example, “Example 1” described in NPL 3 will be described. In “Example 1”, when a message M is composed of seven items, (M[1], M[2], . . . , M[7]) is decomposed into three subsequences as follows.
            S      ⁡              [        1        ]              =          (                        M          ⁡                      [            1            ]                          ,                  M          ⁡                      [            2            ]                          ,                  M          ⁡                      [            3            ]                          ,                  M          ⁡                      [            4            ]                              )                  S      ⁡              [        2        ]              =          (                        M          ⁡                      [            1            ]                          ,                  M          ⁡                      [            2            ]                          ,                  M          ⁡                      [            5            ]                          ,                  M          ⁡                      [            6            ]                              )                  S      ⁡              [        3        ]              =          (                        M          ⁡                      [            1            ]                          ,                  M          ⁡                      [            3            ]                          ,                  M          ⁡                      [            5            ]                          ,                  M          ⁡                      [            7            ]                              )      
Then, the MAC is applied to each of the subsequences, and three tags are computed as follows.    T[1]=MAC(S [1]),    T[2]=MAC(S [2]),    T[3]=MAC(S [3])
In this example, it becomes possible to reduce the number of tags to three, whereas for the case of applying a MAC to each item seven tags are required. Further, when a verification result for each (T[i], S[i]) at a time of verification is expressed by using a binarized value B[i] (that is, if “0”, a MAC is correct; if “1”, falsified), the falsified position can be identified as follows. In other words, when a result of checking a MAC tag for a message M at a certain point of time is as follows,    B[1]=0,    B[2]=1,    B[3]=0since M[6] is an item contained in only B[2] whose result is “1”, it can be identified that M[6] has been falsified. More accurately, in this example, in a case of falsification of one arbitrary item, the falsified item can be identified.
This nature indicates that when the number of falsified items is equal to or less than a given threshold value, the falsified items can be identified from the subsequences created in an efficient manner.
As described in NPL 3, which subsequences are needed and which falsified items can be identified as a result of decomposition are closely related to a combinatorial issue called combinatorial group testing (hereinafter, referred to as “CGT”).
In CGT consisting of m items and s tests, an s-by-m binary matrix W (herein, called a “CGT matrix”) is constructed, and testing is carried out in accordance with W. In other words, when the element in j-th row and i-th column of W is 1, this indicates that j-th test includes i-th item for testing.
When thinking about application to a database system, for example, a person who commits a fraud is unlikely to falsify a large amount of items at one time because of an actual restriction on the system or the like. Thus, combining CGT and MAC in this manner makes it possible to construct a database system capable of identifying a position of actually probable falsification with reduced total number of tags. Note that the nature of being capable of detecting, in regard to arbitrary falsification, the fact that the falsification has been committed is also found in the case of combining CGT and MAC similarly to the case of normal MAC.
Herein, as in Corruption-localizing hashing described in NPL 4, even when an unkeyed hash function is used instead of MAC, a similar effect can be expected under the premise that a hash value is stored in a secure place different from a message. In addition, even though an falsified item cannot be identified, it is usually possible to narrow down a range which may possibly falsified.
NPL 5 discloses a method of constructing tests with use of a coding theory. NPL 6 discloses Parallelizable MAC (PMAC) using n-bit blockcipher E.